class Solution {//leetcode974——和可被k整除的子数组
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n=nums.size();
        int sum=0;
        int cnt=0;
        unordered_map<int,int> hash;
        hash[0]=1;

        for(int i=0;i<n;i++){//前缀和
            sum+=nums[i];
            int index=(sum%k+k)%k;
            if(hash.count(index)) cnt+=hash[index];
            hash[index]++; 
        }
        return cnt;
    }
};